#include <bits/stdc++.h>
using namespace std;
struct Weight
{   //权值
    int price;
    int pathLength;
};

struct Road
{
    vector<int> path;
    int len = 0;
    int price = 0;
};
class Solution
{
private:
    vector<Road> paths;

public:
    vector<Road> allPathsSourceTarget(vector<vector<Weight>> &graph, int start, int target)
    {
        Road road;
        vector<int> visited(graph.size(), 0);
        travelGraph(graph, start, target, road, visited, 0, 0);

        return paths;
    }

    void travelGraph(vector<vector<Weight>> &graph, int vertex, int target, Road road, vector<int> visited, int price, int len)
    {
        if (vertex == target)
        {
            visited[vertex] = 1;

            road.path.push_back(vertex);
            road.len += len;
            road.price += price;
            paths.push_back(road);

            return;
        }

        visited[vertex] = 1;
        road.path.push_back(vertex);
        road.len += len;
        road.price += price;
        for (int i = 0; i < graph.size(); i++)
        {
            if (visited[i] == 0 && graph[vertex][i].pathLength != -1)
            {
                travelGraph(graph, i, target, road, visited, graph[vertex][i].price, graph[vertex][i].pathLength);
            }
        }

        return;
    }
};
int main()
{
    vector<vector<Weight>> graph;
    graph.resize(5);
    for (int i = 0; i < graph.size(); i++)
    {
        graph[i].resize(5);
        for (int j = 0; j < graph[i].size(); j++)
        {
            Weight weight;
            weight.pathLength = -1;
            weight.price = 0;
            if (i == j)
            {
                weight.pathLength = 0;
            }
            graph[i][j] = weight;
        }
    }

    for (int i = 0; i < 6; i++)
    {
        int start;
        int target;
        Weight weightInput;
        cin >> start >> target >> weightInput.pathLength >> weightInput.price;
        graph[start][target] = weightInput;
        graph[target][start] = weightInput;
    }

    Solution solution;

    vector<Road> res = solution.allPathsSourceTarget(graph, 0, 4);

    for (int i = 0; i < res.size(); i++)
    {
        Road road = res[i];

        cout << "path: ";
        for (int j = 0; j < road.path.size(); j++)
        {
            cout << road.path[j];
            if (j != road.path.size() - 1)
            {
                cout << "->";
            }
        }

        cout << endl;
    }

    system("pause");
    return 0;
}